package recursive;

import beans.TreeNode;

/**
 * @author pengfei.hpf
 * @date 2020/3/7
 * @verdion 1.0.0
 */
public class BuildTree {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0){
            return null;
        }
        return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length -1);
    }

    private int findIndex(int[] nums, int num, int start, int end){
        for(int i = start; i <= end; i ++ ){
            if(nums[i] == num){
                return i;
            }
        }
        return -1;
    }

    private TreeNode build(int[] preorder, int[] inorder, int ps, int pe, int is, int ie){
        if(ps > pe || is > ie){
            return null;
        }
        TreeNode root = new TreeNode(preorder[ps]);
        int rootIndex = findIndex(inorder, preorder[ps], is, ie);
        ps++;
        root.left = build(preorder, inorder, ps, pe, is, rootIndex -1);
        ps = ps + rootIndex - is;
        root.right = build(preorder, inorder, ps, pe, rootIndex + 1, ie);
        return root;
    }
}
